package com.zdp.leetcodeMiddle;


import com.zdp.util.ListNode;

/*
* 题目描述：
* 给你一个链表的头节点 head 和一个特定值 x ，
* 请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
提示：
链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 分隔链表_86 {

    /*
    * 解题思路：
    * 如果只是单纯的分隔，可以利用快排中找枢纽的思想
    *  但它还要保留 每个节点的 初始相对位置 ---> 不要交换 直接插入即可 就可以保证 相对位置了
    * */
    public ListNode partition(ListNode head, int x) {
        if(head == null){
            return null;
        }
        ListNode root = new ListNode ();
        root.next = head;
        ListNode p1 = root;
        ListNode pre = root;
        ListNode p = head;
        while(p != null){
            if(p.val < x){
                if(p1.next == p){
                    pre = p;
                    p = p.next;
                }else{
                    // 先删除
                    pre.next = p.next;
                    // 再插入
                    p.next = p1.next;
                    p1.next = p;
                    p = pre.next;
                }
                p1 = p1.next;
            }else{
                pre = p;
                p = p.next;
            }
        }
        return root.next;
    }
}
